#!sicp
(define (square x) (* x x))

;2.1
(define (make-rat n d)
    (let ((g (gcd n d)))
        (if (< d 0)
            (cons (- (/ n g)) (- (/ d g))))
            (cons (/ n g) (/ d g))))
(define (numer x) (car x))
(define (denom x) (cdr x))
(define (add-rat x y)
    (make-rat (+ (* (numer x) (denom y))
                 (* (numer y) (denom x)))
              (* (denom x) (denom y))))
(define (print-rat x)
    (newline)
    (display (numer x))
    (display "/")
    (display (denom x)))

(define one-half (make-rat (- 1) 2))
(define third-half (make-rat 1 3))
(print-rat (add-rat one-half third-half))

;2.2
(define (make-segment start-point end-point)
  (cons start-point end-point))

(define (start-segment seg)
  (car seg))
(define (end-segment seg)
  (cdr seg))

(define (make-point x y)
  (cons x y))
(define (x-point p)
  (car p))
(define (y-point p)
  (cdr p))

(define (midpoint-segment seg)
  (let ((start (start-segment seg))
        (end (end-segment seg)))
    (make-point (average (x-point start)
                         (x-point end))
                (average (y-point start)
                         (y-point end)))))

(define (average x y)
  (/ (+ x y)
     2.0))

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

;2.3
;计算周长
(define (perimeter-rectangle r)
  (let ((length (length-of-rectangle r))
        (width (width-of-rectangle r)))
    (* 2 (+ length width))))
;计算面积
(define (area-rectangle r)
  (* (length-of-rectangle r)
     (width-of-rectangle r)))
;构建矩形
(define (make-rectangle length1 length2 width1 width2)
  (cons (cons length1 length2)
        (cons width1 width2)))
;获取长度和宽度
(define (length1-rectangle r)
  (car (car r)))
(define (length2-rectangle r)
  (cdr (car r)))
(define (width1-rectangle r)
  (car (cdr r)))
(define (width2-rectangle r)
  (cdr (cdr r)))

(define (length-of-rectangle r)
  (let ((length (length1-rectangle r)))
    (let ((start (start-segment length))
          (end (end-segment length)))
      (- (x-point end)
         (x-point start)))))
(define (width-of-rectangle r)
  (let ((width (width1-rectangle r)))
    (let ((start (start-segment width))
          (end (end-segment width)))
      (- (y-point end)
         (y-point start)))))

;测试
(define length1 (make-segment (make-point 1 4)
                              (make-point 4 4)))
(define length2 (make-segment (make-point 1 2)
                              (make-point 4 2)))
(define width1 (make-segment (make-point 1 2)
                             (make-point 1 4)))
(define width2 (make-segment (make-point 4 2)
                             (make-point 4 4)))
(define rectangle (make-rectangle length1 length2 width1 width2))

(define my-list (list 1 2 3 4 5))

(define (list-ref item n)
  (if (= n 0)
      (car item)
      (list-ref (cdr item) (- n 1))))

(define (list-length item)
;;   (if (null? item)
;;       0
;;       (+ 1 (list-length (cdr item)))))
  (define (iter l count)
    (if (null? l)
        count
        (iter (cdr l) (+ 1 count))))
  (iter item 0))

(define (list-append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (list-append (cdr list1) list2))))
;2.17
;; (define (list-last item)
;;   (if (= 2 (list-length item))
;;       (cdr item)
;;       (list-last (cdr item))))

(define (list-last item)
  (define (iter l i)
    (if (null? l)
        i
        (iter (cdr l) (car l))))
  (iter item (car item)))

;2.18
(define (list-reverse item)
  (define (iter remained-item result)
    (if (null? remained-item)
        result
        (iter (cdr remained-item)
              (cons (car remained-item) result))))
  (iter item '()))

;2.20
;; (define (square-list items)
;;   (if (null? items)
;;       '()
;;       (cons (square (car items))
;;             (square-list (cdr items)))))

(define (count-leaves x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

(define (deep-reverse tree)
  (cond ((null? tree)
         '())
        ((not (pair? tree))
         tree)
        (else
         (reverse (list (deep-reverse (car tree))
                        (deep-reverse (cadr tree)))))))
         
(define (fringe tree)
  (cond ((null? tree)
         '())
        ((not (pair? tree))
         (list tree))
        (else
         (append (fringe (car tree))
                 (fringe (cdr tree))))))
;2.29
(define (make-mobile left right)
  (list left right))
(define (make-branch length structure)
  (list length structure))
(define (left-branch mobile)
  (car mobile))
(define (right-branch mobile)
  (cadr mobile))
(define (branch-length branch)
  (car branch))
(define (branch-structure branch)
  (cadr branch))

(define (total-weight mobile)
  (+ (branch-weight (left-branch mobile))
     (branch-weight (right-branch mobile))))
(define (branch-weight branch)
  (if (hangs-another-mobile? branch)
      (total-weight (branch-structure branch))
      (branch-structure branch)))
(define (hangs-another-mobile? branch)
  (pair? (branch-structure branch)))

(define (branch-torque branch)
  (* (branch-length branch)
     (branch-weight branch)))
(define (mobile-balance? mobile)
  (let ((left (left-branch mobile))
        (right (right-branch mobile)))
    (and
     (same-torque? left right)
     (branch-balance? left)
     (branch-balance? right))))
(define (same-torque? left right)
  (=
   (branch-torque left)
   (branch-torque right)))
(define (branch-balance? branch)
  (if (hangs-another-mobile? branch)
      (mobile-balance? (branch-structure branch))
      #t))
;2.30
;; (define (square-tree tree)
;;   (cond ((null? tree)
;;          '())
;;         ((not (pair? tree))
;;          (square tree))
;;         (else
;;          (cons (square-tree (car tree))
;;                (square-tree (cdr tree))))))

(define (square-tree tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (square-tree sub-tree)
             (square sub-tree)))
       tree))
;2.31
;; (define (tree-map f tree)
;;   (cond ((null? tree)
;;          '())
;;         ((not (pair? tree))
;;          (f tree))
;;         (else
;;          (cons (tree-map f (car tree))
;;                (tree-map f (cdr tree))))))

(define (tree-map f tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (tree-map f sub-tree)
             (f sub-tree)))
       tree))

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

(define (accumulate op initial sequence)
    (if (null? sequence)
        initial
        (op (car sequence)
            (accumulate op initial (cdr sequence)))))

(define (enumerate-interval low high)
  (if (< high low)
      nil
      (cons low (enumerate-interval (+ 1 low) high))))
  
(define (enumerate-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))

(define (sum-odd-sequence tree)
  (accumulate +
              0
              (map square
                   (filter odd?
                           (enumerate-tree tree)))))

(define (even-fibs n)
  (accumulate cons
              nil
              (filter even?
                      (map fib
                           (enumerate-interval 0 n)))))

;; (define (fib n)
;;   (cond ((= 0 n) 0)
;;         ((= 1 n) 1)
;;         (else (+ (fib (- n 1))
;;                  (fib (- n 2))))))
(define (fib n)
  (define (iter a b count)
    (if (= count 0)
        b
        (iter (+ a b) a (- count 1))))
  (iter 1 0 n))

(define (prime? n)
  (= n (smallest-divisor n)))
(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))
  
(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))
(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))
(define (make-pair-sum pair)
  (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))
(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (flatmap
                (lambda (i)
                  (map (lambda (j) (list i j))
                       (enumerate-interval 1 (- n 1))))
                (enumerate-interval 1 n)))))

;2.3.2符号求导
(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
          (make-product (multiplier exp)
                        (deriv (multiplicand exp) var))
          (make-product (deriv (multiplier exp) var)
                        (multiplicand exp))))
        ((exponentiation? exp)
         (let ((n (exponent exp))
               (u (base exp)))
           (make-product
            n
            (make-product
             (make-exponentiation u (- n 1))
             (deriv u var)))))
        (else
         (error "unkown expression type -- DERIV" exp))))
(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2))
         (+ a1 a2))
        (else (list '+ a1 a2))))
(define (=number? exp num)
  (and (number? exp) (= exp num)))
(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list '* m1 m2))))
(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))
(define (addend s) (cadr s))
(define (augend s) (caddr s))
(define (product? x)
  (and (pair? x) (eq? (car x) '*)))
(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))
(define (make-exponentiation base exponent)
  (cond ((= exponent 0) 1)
        ((= exponent 1) base)
        (else (list '** base exponent))))
(define (exponentiation? x)
  (and (pair? x)
       (eq? (car x) '**)))
(define (base exp)
  (cadr exp))
(define (exponent exp)
  (caddr exp))

;2.3.3
(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))))
(define (adjoin-set x set)
  (if (element-of-set? x set) set
      (cons x set)))
(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))
;; (define (union-set set1 set2)
;;   (cond ((null? set1) set2)
;;         ((null? set2) set1)
;;         ((not (element-of-set? (car set1) set2))
;;          (cons (car set1)
;;                (union-set (cdr set1) set2)))
;;         (else (union-set (cdr set1) set2))))
(define (union-set set1 set2)
  (define (iter input result)
    (if (null? input)
        (reverse result)
        (let (( current-element (car input))
              (remain-element (cdr input)))
          (if (element-of-set? current-element result)
              (iter remain-element result)
              (iter remain-element
                    (cons current-element result))))))
  (iter (append set1 set2) '()))

(define (entry tree) (car tree))
(define (left-branch-tree tree) (cadr tree))
(define (right-branch-tree tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))
;将树转换为表
(define (tree-list-1 tree)
  (if (null? tree) '()
      (append (tree-list-1 (left-branch-tree tree))
              (cons (entry tree)
                    (tree-list-1 (right-branch-tree tree))))))
(define (tree-list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree) result-list
        (copy-to-list (left-branch-tree tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch-tree tree)
                                          result-list)))))
  (copy-to-list tree '()))

;huffman编码
(define (make-leaf symbol weight)
  (list 'leaf symbol weight))
(define (leaf? object)
  (eq? (car object) 'leaf))
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))
(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right))))
(define (symbols tree)
  (if (leaf? tree)
      (list (symbol-leaf tree))
      (caddr tree)))
(define (weight tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))

;2.4.1
(define (add-complex z1 z2)
  (make-from-real-imag (+ (real-part z1) (real-part z2))
                       (+ (imag-part z1) (imag-part z2))))
  
